' Written by Craig'n'Dave
Module Module1
    ' Quicksort using the Lomuto partition scheme
    Function quicksort(items As List(Of String))
        ' A single item does not need sorting
        If items.Count <= 1 Then
            Return items
        Else
            ' Set the pointer position and pivot to be the last item
            Dim pointer1 As Integer
            Dim pointer2 As Integer = 0
            Dim pivot_value As String = items(items.Count - 1)
            Dim temp As String
            ' Partitioning step
            For pointer1 = 0 To items.Count - 1
                If items(pointer1) < pivot_value Then
                    temp = items(pointer2)
                    items(pointer2) = items(pointer1)
                    items(pointer1) = temp
                    pointer2 = pointer2 + 1
                End If
            Next
            ' Put pivot item in position
            temp = items(pointer2)
            items(pointer2) = pivot_value
            items(items.Count - 1) = temp

            ' Divide and conquer left and right of the pivot
            Dim new_list As New List(Of String)
            new_list.AddRange(quicksort(items.GetRange(0, pointer2)))
            new_list.Add(items(pointer2))
            new_list.AddRange(quicksort(items.GetRange(pointer2 + 1, items.Count() - 1 - pointer2)))
            Return new_list
        End If
    End Function

    'Main algorithm starts here
    Sub Main()
        Dim items As New List(Of String) From {"Florida", "Georgia", "Delaware", "Alabama", "California"}
        items = quicksort(items)
        Console.WriteLine(String.Join(", ", items))
    End Sub
End Module
